home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / util / keys.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  7.2 KB  |  329 lines
  1.  
  2. /*     
  3.  *      FILE
  4.  *         keys
  5.  *     
  6.  *      DECLARATION
  7.  *         Key manipulation routines
  8.  *     
  9.  *      EXPORTS
  10.  *             match-indexkey-operand
  11.  *             equal_indexkey_var
  12.  *             extract-subkey
  13.  *             samekeys
  14.  *             collect-index-pathkeys
  15.  *             match-sortkeys-pathkeys
  16.  *             valid-sortkeys
  17.  *             valid-numkeys
  18.  *    $Header: /private/postgres/src/planner/util/RCS/keys.c,v 1.13 1992/07/04 04:03:51 mao Exp $
  19.  */
  20.  
  21. #include "tmp/c.h"
  22. #include "nodes/pg_lisp.h"
  23. #include "planner/internal.h"
  24. #include "nodes/nodes.h"
  25. #include "nodes/relation.h"
  26. #include "nodes/relation.a.h"
  27. #include "planner/keys.h"
  28. #include "utils/log.h"
  29. #include "planner/tlist.h"
  30.  
  31.  
  32.  
  33. /*    
  34.  *        1. index key
  35.  *            one of:
  36.  *                attnum
  37.  *                (attnum arrayindex)
  38.  *        2. path key
  39.  *            (subkey1 ... subkeyN)
  40.  *                where subkeyI is a var node
  41.  *            note that the 'Keys field is a list of these
  42.  *        3. join key
  43.  *            (outer-subkey inner-subkey)
  44.  *                where each subkey is a var node
  45.  *        4. sort key
  46.  *            one of:
  47.  *                SortKey node
  48.  *                number
  49.  *                nil
  50.  *            (may also refer to the 'SortKey field of a SortKey node,
  51.  *             which looks exactly like an index key)
  52.  *    
  53.  */
  54.  
  55. /*    
  56.  *        match-indexkey-operand
  57.  *    
  58.  *        Returns t iff an index key 'index-key' matches the given clause 
  59.  *        operand.
  60.  *    
  61.  */
  62.  
  63. /*  .. in-line-lambda%598037345, match-index-orclause
  64.  */
  65.  
  66. bool
  67. match_indexkey_operand (indexkey,operand,rel)
  68.      LispValue indexkey;
  69.      Var operand;
  70.      Rel rel;
  71.  
  72. {
  73.     if (IsA (operand,Var) &&
  74.     (CInteger(CAR(get_relids (rel))) == get_varno (operand))&&
  75.     equal_indexkey_var (indexkey,operand))
  76.       return(true);
  77.     else
  78.       return(false);
  79. }
  80.  
  81. /*    
  82.  *        equal_indexkey_var
  83.  *    
  84.  *        Returns t iff an index key 'index-key' matches the corresponding 
  85.  *        fields of var node 'var'.
  86.  *    
  87.  */
  88.  
  89. /*  .. in-line-lambda%598037345, in-line-lambda%598037462
  90.  *  .. match-indexkey-operand
  91.  */
  92. bool
  93. equal_indexkey_var (index_key,var)
  94.      LispValue index_key;
  95.      Var var ;
  96. {
  97.     if (CInteger(index_key) == get_varattno (var))
  98.       return(true);
  99.     else
  100.       return(false);
  101. }
  102.  
  103. /*    
  104.  *        extract-subkey
  105.  *    
  106.  *        Returns the subkey in a join key corresponding to the outer or inner
  107.  *        relation.
  108.  *    
  109.  */
  110.  
  111. /*  .. extract-path-keys, in-line-lambda%598037445, in-line-lambda%598037447
  112.  */
  113. LispValue
  114. extract_subkey (jk,which_subkey)
  115.      JoinKey jk;
  116.      int which_subkey ;
  117. {
  118.      LispValue retval;
  119.  
  120.      switch (which_subkey) {
  121.     case OUTER: 
  122.      retval = (LispValue)get_outer(jk);
  123.      break;
  124.        case INNER: 
  125.      retval = (LispValue)get_inner(jk);
  126.      break;
  127.        default: /* do nothing */
  128.      elog(DEBUG,"extract_subkey with neither INNER or OUTER");
  129.      retval = LispNil;
  130.      }
  131.      return(retval);
  132. }
  133.  
  134. /*    
  135.  *        samekeys
  136.  *    
  137.  *        Returns t iff two sets of path keys are equivalent.  They are 
  138.  *        equivalent if the first subkey (var node) within each sublist of 
  139.  *        list 'keys1' is contained within the corresponding sublist of 'keys2'.
  140.  *    
  141.  *        XXX     It isn't necessary to check that each sublist exactly contain 
  142.  *            the same elements because if the routine that built these
  143.  *            sublists together is correct, having one element in common 
  144.  *            implies having all elements in common.
  145.  *    
  146.  */
  147.  
  148. /*  .. in-line-lambda%598037501
  149.  */
  150. bool
  151. samekeys (keys1,keys2)
  152.      LispValue keys1,keys2 ;
  153. {
  154.      bool allmember = true;
  155.      LispValue key1,key2;
  156.  
  157.      for(key1=keys1,key2=keys2 ; key1 != LispNil && key2 !=LispNil ; 
  158.      key1 = CDR(key1), key2=CDR(key2)) 
  159.       if ( ! member( CAR(key1),CAR(key2)))
  160.         allmember = false;
  161.  
  162.      if ( (length (keys2) >= length (keys1)) && allmember)
  163.        return(true);
  164.      else
  165.        return(false);
  166. }
  167.  
  168. /*    
  169.  *        collect-index-pathkeys
  170.  *    
  171.  *        Creates a list of subkeys by retrieving var nodes corresponding to
  172.  *        each index key in 'index-keys' from the relation's target list
  173.  *        'tlist'.  If the key is not in the target list, the key is irrelevant
  174.  *        and is thrown away.  The returned subkey list is of the form:
  175.  *            ((var1) (var2) ... (varn))
  176.  *    
  177.  *        'index-keys' is a list of index keys
  178.  *        'tlist' is a relation target list
  179.  *    
  180.  *        Returns the list of cons'd subkeys.
  181.  *    
  182.  */
  183.  
  184. /* used by collect_index_pathkeys .  This function is
  185.  * identical to matching_tlvar and tlistentry_member.
  186.  * They should be merged.
  187.  */
  188.  
  189. Expr
  190. matching2_tlvar(var,tlist,test)
  191.      LispValue tlist;
  192.      Var var;
  193.      bool (*test)();
  194. {
  195.     LispValue tlentry = LispNil;
  196.  
  197.     if (var) {
  198.     LispValue temp = LispNil;
  199.     foreach (temp,tlist) {
  200.         if ( (*test)(var, get_expr(get_entry(CAR(temp))))) {
  201.         tlentry = CAR(temp);
  202.         break;
  203.         }
  204.     }
  205.     }
  206.  
  207.     if ( tlentry ) 
  208.       return((Expr)get_expr (get_entry (tlentry)) );
  209.     else
  210.       return((Expr)NULL);
  211. }
  212.  
  213. /*  .. create_index_path   */
  214.  
  215.     LispValue
  216. collect_index_pathkeys (index_keys,tlist)
  217.      LispValue index_keys,tlist ;
  218. {
  219.     LispValue index_key,retval = LispNil;
  220.     
  221.     foreach(index_key,index_keys) {
  222.     if (CInteger(CAR(index_key)) != 0) {
  223.         Expr mvar;
  224.         mvar = matching2_tlvar (CAR(index_key),tlist,equal_indexkey_var);
  225.         if ( mvar ) 
  226.           retval = nconc(retval,lispCons( lispCons((LispValue)mvar,LispNil),
  227.                           LispNil));
  228.     }
  229.     }
  230.     return(retval);
  231. }
  232.  
  233. /*    
  234.  *        match-sortkeys-pathkeys
  235.  *    
  236.  *        Returns t iff the sort required by a result as specified by
  237.  *        'relid' and 'sortkeys' matches the 'pathkeys' of a path.
  238.  *    
  239.  */
  240.  
  241. /*  .. sort-relation-paths
  242.  */
  243. #define every2(a,x,b,y) for(a=x,b=y;a!=LispNil&&b!=LispNil;a=CDR(a),b=CDR(b))
  244.  
  245. bool
  246. match_sortkeys_pathkeys (relid,sortkeys,pathkeys)
  247.      LispValue relid,sortkeys,pathkeys ;
  248. {
  249.      /* declare (special (relid)); */
  250.      LispValue sortkey,pathkey;
  251.      bool every_val = true;
  252.  
  253.      every2 (sortkey,sortkeys, pathkey,pathkeys) {
  254.       if ( ! equal_sortkey_pathkey (relid,CAR(sortkey),CAR(pathkey)))
  255.         every_val = false;
  256.      }
  257.  
  258.      if ( every_val  && (length (pathkeys) >= length (sortkeys)))
  259.        return(true);
  260.      else
  261.        return(false);
  262. }
  263.  
  264. /*    
  265.  *        equal-sortkey-pathkey
  266.  *    
  267.  *        Returns t iff a sortkey as specified by 'relid' and 'sortkey' matches
  268.  *        one of the subkeys (var nodes) within 'pathkey'.
  269.  *    
  270.  */
  271.  
  272. /*  .. in-line-lambda%598037461
  273.  */
  274.  
  275. bool
  276. equal_sortkey_pathkey (relid,sortkey,pathkey)
  277.      LispValue relid,sortkey,pathkey ;
  278. {
  279.      /* declare (special (relid,sortkey)); */
  280.      LispValue subkey;
  281.      bool retval = false;
  282.  
  283.      foreach(subkey,pathkey) {
  284.       if (equal ((Node)relid,(Node)get_varno ((Var)CAR(subkey))) &&
  285.           equal_indexkey_var (sortkey,(Var)CAR(subkey)))
  286.         retval = true;
  287.      }
  288.      return(retval);
  289. }
  290.  
  291. /*    
  292.  *        valid-sortkeys
  293.  *    
  294.  *        Returns t if 'sortkeys' appears to be a valid SortKey node.
  295.  *    
  296.  */
  297.  
  298. /*  .. find-index-paths, query_planner, subplanner
  299.  */
  300.  
  301. bool
  302. valid_sortkeys (node)
  303.      LispValue node ;
  304. {
  305.     if (node)
  306.       return ((bool)NodeIsType(node, T_SortKey));
  307.     else
  308.       return(false);   /* if sortkeys is nil  */
  309. }
  310.  
  311. /*    
  312.  *        valid-numkeys
  313.  *    
  314.  *        Returns t if 'sortkeys' appears to be a valid numkeys value
  315.  *    
  316.  */
  317.  
  318. /*  .. query_planner
  319.  */
  320. bool
  321. valid_numkeys (sortkeys)
  322.      LispValue sortkeys ;
  323. {
  324.      if ( integerp (sortkeys) && CInteger(sortkeys) <= _MAX_KEYS_)
  325.        return(true);
  326.      else
  327.        return(false);
  328. }
  329.